//你有两个字符串，即pattern和value。 pattern字符串由字母"a"和"b"组成，用于描述字符串中的模式。例如，字符串
//"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，"go"是"b"），该字符串也匹配像"a"、"ab"和"b"这样的模式。但需注意"a"和"b"不能同时表示相
//同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。 
//
// 示例 1： 
//
// 输入： pattern = "abba", value = "dogcatcatdog"
//输出： true
// 
//
// 示例 2： 
//
// 输入： pattern = "abba", value = "dogcatcatfish"
//输出： false
// 
//
// 示例 3： 
//
// 输入： pattern = "aaaa", value = "dogcatcatdog"
//输出： false
// 
//
// 示例 4： 
//
// 输入： pattern = "abba", value = "dogdogdogdog"
//输出： true
//解释： "a"="dogdog",b=""，反之也符合规则
// 
//
// 提示： 
//
// 
// 1 <= len(pattern) <= 1000 
// 0 <= len(value) <= 1000 
// 你可以假设pattern只包含字母"a"和"b"，value仅包含小写字母。 
// 
//
// Related Topics 数学 字符串 回溯 枚举 👍 153 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-09-09 21:54:20
 * @description 面试题 16.18.模式匹配
 */
public class PatternMatchingLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 PatternMatchingLcci fun=new PatternMatchingLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*
		 * pattern abba =4=k1*a+k2*b
		 * value  dog1catcatdog1 =12
		 * a+b=6
		 *
		 * a和b各自的个数可以统计出来
		 * 然后枚举a的长度就可以得到b的长度
		 * 然后通过pattern构建value，如果相等就返回
		 * 缺点，需要构建大量字符串
		 * */
		 public boolean patternMatching1(String pattern, String value) {
			 // 统计a和b的数量
			 int countA = 0, countB = 0;
			 for (char ch : pattern.toCharArray()) {
				 if (ch == 'a') countA++;
				 else countB++;
			 }

			 int lenP = pattern.length();
			 int lenV = value.length();

			 // 如果value为空，pattern必须只有一种字符或者为空
			 if (lenV == 0) {
				 return countA == 0 || countB == 0;
			 }

			 // 如果pattern为空，value也必须为空
			 if (lenP == 0) {
				 return lenV == 0;
			 }

			 // 尝试所有可能的a的长度
			 for (int lenA = 0; lenA <= lenV; lenA++) {
				 // 计算b需要的长度
				 if (countB == 0) {
					 // 只有a的情况
					 if (countA * lenA != lenV) continue;
				 } else {
					 // 有a和b的情况
					 if ((lenV - countA * lenA) % countB != 0) continue;
				 }

				 int lenB = countB == 0 ? 0 : (lenV - countA * lenA) / countB;
				 if (lenB < 0) continue;

				 if (check(lenA, lenB, pattern, value)) {
					 return true;
				 }
			 }

			 return false;
		 }
	public boolean patternMatching(String pattern, String value) {
		// 统计a和b的数量
		int countA = 0, countB = 0;
		for (char ch : pattern.toCharArray()) {
			if (ch == 'a') countA++;
			else countB++;
		}

		int lenP = pattern.length();
		int lenV = value.length();

		// 边界条件处理
		if (lenV == 0) return countA == 0 || countB == 0;
		if (lenP == 0) return lenV == 0;

		// 优化：根据a和b的数量分别处理
		if (countA == 0) {
			// 只有b的情况
			if (lenV % countB != 0) return false;
			int lenB = lenV / countB;
			return check(0, lenB, pattern, value);
		} else if (countB == 0) {
			// 只有a的情况
			if (lenV % countA != 0) return false;
			int lenA = lenV / countA;
			return check(lenA, 0, pattern, value);
		}
		if (countA <= countB) {
			// 既有a又有b的情况，优化循环范围
			for (int lenA = 0; lenA <= lenV / countA; lenA++) {
				int remaining = lenV - countA * lenA;
				if (remaining % countB != 0) continue;
				int lenB = remaining / countB;
				if (lenB < 0) continue;

				if (check(lenA, lenB, pattern, value)) {
					return true;
				}
			}
		} else {
			// 也可以反过来，先尝试b的长度
			for (int lenB = 0; lenB <= lenV / countB; lenB++) {
				int remaining = lenV - countB * lenB;
				if (remaining % countA != 0) continue;
				int lenA = remaining / countA;
				if (lenA < 0) continue;

				if (check(lenA, lenB, pattern, value)) {
					return true;
				}
			}
		}
		return false;
	}

	private boolean check(int lenA, int lenB, String pattern, String value) {
		String aPattern = null;
		String bPattern = null;
		int index = 0;

		for (char ch : pattern.toCharArray()) {
			if (ch == 'a') {
				String current = value.substring(index, index + lenA);
				if (aPattern == null) {
					aPattern = current;
				} else if (!aPattern.equals(current)) {
					return false;
				}
				index += lenA;
			} else {
				String current = value.substring(index, index + lenB);
				if (bPattern == null) {
					bPattern = current;
				} else if (!bPattern.equals(current)) {
					return false;
				}
				index += lenB;
			}

			// 检查a和b是否相同
			if (aPattern != null && bPattern != null && aPattern.equals(bPattern)) {
				return false;
			}
		}

		return true;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
